2010년04월10일 19번

[과목 구분 없음]
정렬 알고리즘에 대한 설명으로 옳지 않은 것은?

① 합병 정렬은 히프 정렬에 비해서 더 많은 기억 장소가 필요하다.
② 퀵 정렬 알고리즘의 수행시간은 최악의 경우 O(n2)이다.
③ 히프 정렬 알고리즘의 수행시간은 최악의 경우 O(log n)이다.
④ 삽입 정렬은 정렬할 자료가 이미 어느 정도 정렬되어 있는 경우 효과적이다.

(정답률: 64%)

문제 해설

"히프 정렬 알고리즘의 수행시간은 최악의 경우 O(log n)이다."가 옳은 설명입니다. 이유는 히프 정렬에서는 최대 힙을 구성하는 데 O(log n)의 시간이 걸리고, 이를 n번 반복하므로 전체 시간 복잡도는 O(n log n)입니다. 따라서 최악의 경우에도 O(log n)의 시간 복잡도를 가집니다.

이전 문제 다음 문제